#include <iostream>
#include <vector>
#include <cassert>

using namespace std;
// 240. 搜索二维矩阵 II
// 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
//每行的元素从左到右升序排列。
//每列的元素从上到下升序排列。
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        assert(matrix.size()>0);
        assert(matrix[0].size()>0);
        int row = 0;
        int column = matrix[0].size() - 1;
        while(row < matrix.size() && column >= 0) {
            if(matrix[row][column] == target)   // 找到目标值
                return true;
            if(matrix[row][column] > target)
                column--;   // 比target大，左移
            else
                row++;      // 比target小，下移
        }
        return false;
    }
};
int main() {
    vector<vector<int>> matrix({{1,4,7,11,15},{2,5,8,12,19},{3,6,9,16,22},{10,13,14,17,24},{18,21,23,26,30}});
    cout <<"Find 6:" << boolalpha << Solution().searchMatrix(matrix,6)<<endl;   // true
    cout <<"Find 24:" << boolalpha  << Solution().searchMatrix(matrix,24)<<endl; // true
    cout <<"Find 22:" << boolalpha  << Solution().searchMatrix(matrix,22)<<endl; // true
    cout <<"Find 20:" << boolalpha  << Solution().searchMatrix(matrix,20)<<endl; // false

    return 0;
}
